//static char rcsid[] = "$Id$" "\n$Id$";
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "assert.h"
#include "fmt.h"
#include "thread.h"
#include "mem.h"
struct args {
	int *a;
	int lb, ub;
};
int cutoff = 10000;
#include <stdarg.h>
#define Fmt_print outs

static void outs(const char *fmt, ...) {
	char *buf;
	va_list_box box;

	va_start(box.ap, fmt);
	buf = Fmt_vstring(fmt, &box);
	va_end(box.ap);
	printf("%s", buf);
	FREE(buf);
}

int partition(int a[], int i, int j) {
	int v, k, t;
	j++;
	k = i;
	v = a[k];
	while (i < j) {
		i++; while (a[i] < v && i < j) i++;
		j--; while (a[j] > v         ) j--;
		if (i < j) { t = a[i]; a[i] = a[j]; a[j] = t; }
	}
	t = a[k]; a[k] = a[j]; a[j] = t;
	return j;
}
//
//int quick(void *cl) {
//	struct args *p = cl;
//	int lb = p->lb, ub = p->ub;
//	if (lb < ub) {
//		int k = partition(p->a, lb, ub);
//		p->lb = lb;
//		p->ub = k - 1;
//		if (k - lb > cutoff) {
//			Thread_T t;
//			t = Thread_new(quick, p, sizeof *p, NULL);
//			Fmt_print("thread %p sorted %d..%d\n", t, lb, k - 1);
//		} else
//			quick(p);
//		p->lb = k + 1;
//		p->ub = ub;
//		if (ub - k > cutoff) {
//			Thread_T t;
//			t = Thread_new(quick, p, sizeof *p, NULL);
//			Fmt_print("thread %p sorted %d..%d\n", t, k + 1, ub);
//		} else
//			quick(p);
//	}
//	return EXIT_SUCCESS;
//}
//void sort(int *x, int n, int argc, char *argv[]) {
//	struct args args;
//	if (argc >= 3)
//		cutoff = atoi(argv[2]);
//	args.a = x;
//	args.lb = 0;
//	args.ub = n - 1;
//	quick(&args);
//	Thread_join(NULL);
//}
//main(int argc, char *argv[]) {
//	int i, n = 100000, *x, preempt;
//	preempt = Thread_init(1, NULL);
//	assert(preempt == 1);
//	if (argc >= 2)
//		n = atoi(argv[1]);
//	x = CALLOC(n, sizeof (int));
//	srand(time(NULL));
//	for (i = 0; i < n; i++)
//		x[i] = rand();
//	sort(x, n, argc, argv);
//	for (i = 1; i < n; i++)
//		if (x[i] < x[i-1])
//			break;
//	assert(i == n);
//	Thread_exit(EXIT_SUCCESS);
//	return EXIT_SUCCESS;
//}
